import com.sun.corba.se.impl.orbutil.graph.Graph;
import com.sun.corba.se.impl.orbutil.graph.GraphImpl;
import com.sun.org.apache.xalan.internal.xsltc.dom.SortingIterator;
import sun.awt.image.ImageWatched;

import java.io.PrintWriter;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 马拉圈
 * Date: 2023-05-03
 * Time: 23:40
 */
public class GraphByMatrix{

    // 1. 顶点集合
    private char[] arrayV;

    //2. 邻接矩阵
    private int[][] matrix;//顶点在这里的下标即在字符数组的下标

    //3. 是否是有向图
    private boolean isDirect;

    /**
     *
     * @param size 【顶点个数】
     * @param isDirect
     */
    public GraphByMatrix(int size, boolean isDirect) {
        this.arrayV = new char[size];
        matrix = new int[size][size];//此时默认都是0
        this.isDirect = isDirect;

        //将邻接矩阵默认值改为【∞】
        for (int i = 0; i < size; i++) {
            Arrays.fill(matrix[i], Integer.MAX_VALUE);
            //fill,让数组充满∞这个值
        }
    }
    public void initArrayV(char[] array) {
        for (int i = 0; i < array.length; i++) {
            arrayV[i] = array[i];
        }
    }

    //获得顶点对应下标
    public int getIndexOfV(char v) {
        for (int i = 0; i < arrayV.length; i++) {
            if(v == arrayV[i]) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 添加边
     * @param v1 起始顶点
     * @param v2 目的顶点
     * @param weight 权值
     */
    public void addEdge(char v1, char v2, int weight) {
        int index1 = getIndexOfV(v1);
        int index2 = getIndexOfV(v2);
        if(index1 != -1 && index2 != -1 && index1 != index2) {
            matrix[index1][index2] = weight; //index1 --> index2
            if(!isDirect) {//无向图
                matrix[index2][index1] = weight;
            }
        }
    }

    //获得顶点的度
    public int getDevOfV(char v) {
        int indexV = getIndexOfV(v);
        int count = 0;
        //无论如何，都要遍历对于行
        for (int i = 0; i < matrix[0].length; i++) {
            if(matrix[indexV][i] != Integer.MAX_VALUE) {
                count++;
            }
        }
        //如果是有向图，则遍历对应列
        if(isDirect) {
            for (int i = 0; i < matrix.length; i++) {
                if(matrix[i][indexV] != Integer.MAX_VALUE) {
                    count++;
                }
            }
        }
        return count;
    }

    //打印邻接矩阵
    public void printGraph() {
        System.out.print("   ");
        for (int i = 0; i < arrayV.length; i++) {
            System.out.print("[" + arrayV[i] + "]");
        }
        System.out.println();
        for (int i = 0; i < matrix.length; i++) {
            System.out.print("[" + arrayV[i] + "]");
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == Integer.MAX_VALUE) {
                    System.out.print(" ∞ ");
                }else {
                    System.out.print(" " + matrix[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    //************************************************************************
    //广度优先遍历
    public void bfs(char v) {
        //标记数组
        boolean[] isVisited = new boolean[arrayV.length];

        //定义一个队列
        Queue<Integer> queue = new LinkedList<>();
        //获取起始顶点的下标
        int index = getIndexOfV(v);
        if(index == -1) {
            return;
        }
        queue.offer(index);
        while(!queue.isEmpty()) {
            int top = queue.poll();
            isVisited[top] = true;
            System.out.print(arrayV[top] + " ");
            for (int i = 0; i < arrayV.length; i++) {
                if(!isVisited[i] && matrix[top][i] != Integer.MAX_VALUE) {
                    queue.offer(i);
                    isVisited[i] = true;//不置为true，会导致D打印两次
                }
            }
        }
    }

    //深度优先遍历
    public void dfs(char v) {
        boolean[] isVisited = new boolean[arrayV.length];
        int src = getIndexOfV(v);dfsOrder(src, isVisited);
    }
    private void dfsOrder(int src, boolean[] isVisited) {
        System.out.print(arrayV[src] + " ");
        isVisited[src] = true;
        for (int i = 0; i < matrix[src].length; i++) {
            if(!isVisited[i] && matrix[src][i] != Integer.MAX_VALUE) {
                dfsOrder(i, isVisited);
            }
        }
    }


    //************************************************************************




    public static void main1(String[] args) {
        char[] chars = {'A', 'B', 'C', 'D'};

        GraphByMatrix graph = new GraphByMatrix(chars.length, true);
        graph.initArrayV(chars);

        graph.addEdge('A', 'B', 1);
        graph.addEdge('A', 'D', 1);
        graph.addEdge('B', 'A', 1);
        graph.addEdge('B', 'C', 1);
        graph.addEdge('C', 'B', 1);
        graph.addEdge('C', 'D', 1);
        graph.addEdge('D', 'A', 1);
        graph.addEdge('D', 'C', 1);
//        graph.printGraph();
//
//        if(graph.isDirect) {
//            System.out.println("有向图：");
//        }else {
//            System.out.println("无向图：");
//        }
//        System.out.println("A节点的度：" + graph.getDevOfV('A'));
//        System.out.println("B节点的度：" + graph.getDevOfV('B'));
//        System.out.println("C节点的度：" + graph.getDevOfV('C'));
//        System.out.println("D节点的度：" + graph.getDevOfV('D'));
//        graph.bfs('B');
//        System.out.println();
        graph.dfs('B');
        System.out.println();
    }

    static class Edge {
        int src;
        int dest;
        int weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    /**
     *
     * @param minTree 最小生成树放在图 minTree中
     * @return 最小生成树的权和
     */
    public int kruskal(GraphByMatrix minTree) {
        //1. 优先级序列存放所有边
        PriorityQueue<Edge> minHeap = new PriorityQueue<Edge>(
                (o1, o2) -> {
                    return o1.weight - o2.weight;
                }
        );
        int n = matrix.length;
        //无向图只需要一条即可
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                minHeap.offer(new Edge(i, j, matrix[i][j]));
            }
        }
        //最终的权值和
        int retWeight = 0;
        //定义并查集
        UnionFindSet unionFindSet = new UnionFindSet(n);
        int size = 0;//已选边的条数
        //选取n-1条边，如果不成环，必然选中n个节点，
        // 如果队列都空了，都没有n-1条边，则不是无向连通图
        while(size < n - 1 && !minHeap.isEmpty()) {
            Edge minEdge = minHeap.poll();
            int src = minEdge.src;
            int dest = minEdge.dest;
            //如果src与dest师出同门，不能添加
            if(!unionFindSet.isSameSet(src, dest)) {
                System.out.println(arrayV[src] +"---"
                        +arrayV[dest]+" : "+matrix[src][dest]);
                //这两个节点建立关系
                unionFindSet.union(src, dest);
                //存放在minTree图中，最小生成树返回到这里面
                minTree.addEdge(arrayV[src], arrayV[dest], minEdge.weight);
                //权值和
                retWeight += minEdge.weight;
                //被选中的边的条数加一
                size++;
            }
        }
        return size == n - 1 ? retWeight : Integer.MAX_VALUE;
    }

    public int prime(GraphByMatrix minTree, char V) {
        //获取顶点的下标
        int srcIndex = getIndexOfV(V);

        //起始节点集合与目的节点集合
        Set<Integer> srcSet = new HashSet<>();
        Set<Integer> destSet = new HashSet<>();

        //初始化两个集合
        srcSet.add(srcIndex);
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            if(i != srcIndex) {
                destSet.add(i);
            }
        }

        //从srcSet到destSet集合的边
        //定义优先级队列与初始化优先级队列
        PriorityQueue<Edge> minHeap = new PriorityQueue<>(
                (o1, o2) -> {
                    return o1.weight - o2.weight;
                    //左大于右为正，为升序小根堆
                }
        );
        for (int i = 0; i < n; i++) {
            if(matrix[srcIndex][i] != Integer.MAX_VALUE) {
                minHeap.offer(new Edge(srcIndex, i, matrix[srcIndex][i]));
            }
        }

        int retWeight = 0;//返回的权值和
        int edgeCount = 0;//已选中的边

        //核心循环
        while(edgeCount < n - 1 && !minHeap.isEmpty()) {
            Edge minEdge = minHeap.poll();
            int src = minEdge.src;
            int dest = minEdge.dest;
            //判断dest是否被标记
            if(!srcSet.contains(dest)) {
                minTree.addEdge(arrayV[src], arrayV[dest], matrix[src][dest]);
                System.out.println(arrayV[src] + "---" + arrayV[dest] + " : "
                + matrix[src][dest]);
                edgeCount++;
                retWeight += matrix[src][dest];

                //目的节点被标记：加入srcSet，在destSet除名
                srcSet.add(dest);
                destSet.remove(dest);

                //添加新增起始顶点的所有直接连通的边
                for (int i = 0; i < n; i++) {
                    if(matrix[dest][i] != Integer.MAX_VALUE && destSet.contains(i)) {
                        minHeap.offer(new Edge(dest, i, matrix[dest][i]));
                    }
                }
            }
        }
        return edgeCount == n - 1 ? retWeight : Integer.MAX_VALUE;
    }


    public static void testGraphMinTree1() {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.initArrayV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix kminTree = new GraphByMatrix(str.length(),false);
        kminTree.initArrayV(array);
        System.out.println(g.kruskal(kminTree));
        kminTree.printGraph();
    }

    public static void testGraphMinTree2() {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.initArrayV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix kminTree = new GraphByMatrix(str.length(),false);
        kminTree.initArrayV(array);
        System.out.println(g.prime(kminTree, 'a'));
        kminTree.printGraph();
    }

//****************************************************************************************************
    //Dijkstra算法

    public void dijkstraBite(char vSrc,int[] dist,int[] pPath) {
//1. 获取顶点下标
        int srcIndex = getIndexOfV(vSrc);
//2、初始化父顶点数组下标为-1
        Arrays.fill(pPath,-1);
//3、初始化dist数组
        Arrays.fill(dist,Integer.MAX_VALUE);
//4、对起点进行初始化,给一个最小值 方便第一次就能找到最小值
        dist[srcIndex] = 0;
//起点的父顶点下标是自己
        pPath[srcIndex] = srcIndex;
//5、定义s为 已经确定的顶点数组的集合 默认为false
        int n = arrayV.length;
        boolean[] s = new boolean[n];
//6、更新N个顶点
        for(int k = 0; k < n;k++) {
//第 1步：找到 srcIndex 到不在S中 路径最短的 那个顶点u
//设最短路径为整数最大值
            int min = Integer.MAX_VALUE;
//顶点srcIndex开始找
            int u = srcIndex;
            for (int i = 0; i < n; i++) {
//如果s集合中i的顶点没有 && 距离也是比最小值小
                if(s[i] == false && dist[i] < min) {
//更新此时的最小值
                    min = dist[i];
//更新此时在U集合找到的顶点
                    u = i;
                }
            }
//每遍历一遍n个顶点，找到最短的顶点U
            s[u] = true;
/*
第2步： 松弛算法：更新一遍u连接的所有边，看是否能更新出更短连接路径
src-u知道了 u连接出去的点u-> v 需要更新 就能知道src-v的值
*/
//在邻接矩阵当中 U连接出去的边可能有N个
            for (int v = 0; v < n; v++) {
//v顶点不能被更新 并且 u->v 是有权值的 并且 加起来的权值 < dist[v]
                if( s[v] == false && matrix[u][v] != Integer.MAX_VALUE
                        && dist[u]+matrix[u][v] < dist[v]) {
//更新当前v顶点 对应 下标
                    dist[v] = dist[u] + matrix[u][v];
                    pPath[v] = u;
                }
            }
        }
    }
    /**
     *
     * @param src 出发点
     * @param dist 要求把最短路径长存放在这个数组里
     * @param path 要求将前面点存放在这个数组里
     */
    public void dijkstra(char src, int[] dist, int[] path) {
        //获取顶点下标
        int srcIndex = getIndexOfV(src);

        //初始化dist
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[srcIndex] = 0;//起始点

        //初始化path
        Arrays.fill(path, -1);
        path[srcIndex] = srcIndex;//如果是前一个顶点是本身的话，则说明到达起始点

        //定义visited数组
        int n = arrayV.length;
        boolean[] visited = new boolean[n];

        //开始标记与松弛操作了
        //由于我们知道每次循环都会标记一个，那么循环次数就知道了，所以我们就用特定的for循环去写
        for (int i = 0; i < n; i++) {

            //找dist最小值
            int index = srcIndex;//这个无所谓
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if(!visited[j] && dist[j] < min) {
                    index = j;
                    min = dist[j];
                }
            }
            //标记
            visited[index] = true;

            //松弛
            for (int j = 0; j < n; j++) {
                //被必要松弛到标记的顶点的，因为没用（再之前的证明中），你要也可以
                if(!visited[j] && matrix[index][j] != Integer.MAX_VALUE
                    && dist[index] + matrix[index][j] < dist[j]) {
                    //松弛导致的更新操作，更新其路径为【0，index】延伸一条边【index，j】
                    dist[j] = dist[index] + matrix[index][j];
                    path[j] = index;
                }
            }
        }
    }

    static class Point {
        int indexV;
        int distValue;

        public Point(int indexV, int distValue) {
            this.indexV = indexV;
            this.distValue = distValue;
        }
    }
    /**
     *
     * @param src 出发点
     * @param dist 要求把最短路径长存放在这个数组里
     * @param path 要求将前面点存放在这个数组里
     */
    public void pQDijkstra(char src,int[] dist,int[] path) {
        //获得顶点下标
        int srcIndex = getIndexOfV(src);
        //初始化dist
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[srcIndex] = 0;//起始点

        //初始化path
        Arrays.fill(path, -1);
        path[srcIndex] = srcIndex;//如果是前一个顶点是本身的话，则说明到达起始点

        //定义visited数组
        int n = arrayV.length;
        boolean[] visited = new boolean[n];

        //定义小根堆
        PriorityQueue<Point> queue = new PriorityQueue<Point>(
                (o1, o2) -> {
                    return o1.distValue - o2.distValue;
                }
        );

        queue.offer(new Point(srcIndex, 0));
        while(!queue.isEmpty()) {
            Point point = queue.poll();
            int index = point.indexV;
            //被标记过，达咩！
            if(visited[index]) {
                continue;
            }
            //标记
            visited[index] = true;
            //松弛
            for (int j = 0; j < n; j++) {
                //被必要松弛到标记的顶点的，因为没用（再之前的证明中），你要也可以
                if(!visited[j] && matrix[index][j] != Integer.MAX_VALUE
                        && dist[index] + matrix[index][j] < dist[j]) {
                    //松弛导致的更新操作，更新其路径为【0，index】延伸一条边【index，j】
                    dist[j] = dist[index] + matrix[index][j];
                    path[j] = index;
                    queue.offer(new Point(j, dist[j]));
                }
            }
        }
    }



    public void printShortPath(char vSrc,int[] dist,int[] pPath) {
//1. 获取顶点下标
        int srcIndex = getIndexOfV(vSrc);
        int n = arrayV.length;
//2、遍历pPath数组 的n个 值，
// 每个值到起点S的 路径都打印一遍
        for (int i = 0; i < n; i++) {
//自己到自己的路径不打印
            if(i != srcIndex) {
                ArrayList<Integer> path = new ArrayList<>();
                int parentI = i;
                while (parentI != srcIndex) {
                    path.add(parentI);
                    parentI = pPath[parentI];
                }
                path.add(srcIndex);
//翻转path当中的路径
                Collections.reverse(path);
                for (int pos : path) {
                    System.out.print(arrayV[pos] +" -> ");
                }
                System.out.println("路径长：" + dist[i]);
            }
        }
    }

    public static void testGraphDijkstra() {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('s', 't', 10);
        g.addEdge('s', 'y', 5);
        g.addEdge('y', 't', 3);
        g.addEdge('y', 'x', 9);
        g.addEdge('y', 'z', 2);
        g.addEdge('z', 's', 7);
        g.addEdge('z', 'x', 6);
        g.addEdge('t', 'y', 2);
        g.addEdge('t', 'x', 1);
        g.addEdge('x', 'z', 4);
/*
搞不定负权值
String str = "sytx";
char[] array = str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(),true);
g.initArrayV(array);
g.addEdge('s', 't', 10);
g.addEdge('s', 'y', 5);
g.addEdge('t', 'y', -7);
g.addEdge('y', 'x', 3);*/

        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        //g.printGraph();
        g.pQDijkstra('s', dist, parentPath);
        g.printShortPath('s', dist, parentPath);
    }



//****************************************************************************************************


    public void queueBellmanFord(char src,int[] dist,int[] path) {
        //获得顶点下标
        int srcIndex = getIndexOfV(src);
        //初始化dist
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[srcIndex] = 0;//起始点

        //初始化path
        Arrays.fill(path, -1);
        path[srcIndex] = srcIndex;//如果是前一个顶点是本身的话，则说明到达起始点

        int n = arrayV.length;

        //定义一个队列
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(srcIndex);

        //开始循环松弛
        while(!queue.isEmpty()) {
            int top = queue.poll();
            for (int i = 0; i < n; i++) {
                if (matrix[top][i] != Integer.MAX_VALUE
                        && matrix[top][i] + dist[top] < dist[i]) {
                    dist[i] = matrix[top][i] + dist[top];
                    path[i] = top;
                    queue.offer(i);
                }
            }
        }
    }

    //这也是判断是否有负权回路的算法
    public boolean bellmanFord(char src,int[] dist,int[] path) {
        //获得顶点下标
        int srcIndex = getIndexOfV(src);
        //初始化dist
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[srcIndex] = 0;//起始点

        //初始化path
        Arrays.fill(path, -1);
        path[srcIndex] = srcIndex;//如果是前一个顶点是本身的话，则说明到达起始点

        int n = arrayV.length;

        //循环n-1次，每次松弛一个顶点
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if(matrix[j][k] != Integer.MAX_VALUE &&
                            matrix[j][k] + dist[j] < dist[k]) {
                        dist[k] = matrix[j][k] + dist[j];
                        path[k] = j;
                    }
                }
            }
        }
        //检测负权回路
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //至于一样短的情况下，无所谓，这就是最短路径不唯一呗~
                if (matrix[i][j] != Integer.MAX_VALUE
                        && matrix[i][j] + dist[i] < dist[j]) {
                    return false; //false代表了有负权回路

                }
            }
        }

        return true;
    }
    public boolean bellmanFordBite(char vSrc,int[] dist,int[] pPath) {
//1. 获取顶点下标
        int srcIndex = getIndexOfV(vSrc);
//2、初始化父顶点数组下标为-1
        Arrays.fill(pPath,-1);
//3、初始化dist数组
        Arrays.fill(dist,Integer.MAX_VALUE);
//4、对起点进行初始化,给一个最小值 方便第一次就能找到最小值
        dist[srcIndex] = 0;
        int n = arrayV.length;
//N个点 遍历n次
        for(int k = 0;k < n;k++) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (matrix[i][j] != Integer.MAX_VALUE
                            && dist[i] + matrix[i][j] < dist[j]) {
//System.out.println(arrayV[i] + "-> " + arrayV[j] + " : " + matrix[i][j]);
                        dist[j] = dist[i] + matrix[i][j];
                        pPath[j] = i;
                    }
                }
            }
        }
//求完之后 再检测一遍 是否还能更新 可以那么就是存在负权回路
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] != Integer.MAX_VALUE
                        && dist[i] + matrix[i][j] < dist[j]) {
                    return false;//存在负权回路
                }
            }
        }
        return true;
    }

    public static void testGraphBellmanFord() {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
         g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', 8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);
//负权回路实例
//        g.addEdge('s', 't', 6);
//        g.addEdge('s', 'y', 7);
//        g.addEdge('y', 'z', 9);
//        g.addEdge('y', 'x', -3);
//        g.addEdge('y', 's', 1);
//        g.addEdge('z', 's', 2);
//        g.addEdge('z', 'x', 7);
//        g.addEdge('t', 'x', 5);
//        g.addEdge('t', 'y', -8);
//        g.addEdge('t', 'z', -4);
//        g.addEdge('x', 't', -2);
        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        g.queueBellmanFord('s', dist, parentPath);
        g.printShortPath('s', dist, parentPath);
    }



//****************************************************************************************************
    public void floydWarShall(int[][] dist, int[][] path) {
        //初始化dist和path
        int n = arrayV.length;
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
            Arrays.fill(path[i], -1);
        }

        //每一个顶点的第一代子图，记录在dist和path中，现在局部的最短路径
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] != Integer.MAX_VALUE) {
                    dist[i][j] = matrix[i][j];
                    path[i][j] = i;//这一行的上一个就是i
                }else {
                    path[i][j] = -1;//不存在路径
                }
                if(i == j) {
                    dist[i][j] = 0;
                    path[i][j] = j;
                }
            }
        }
        //进行算法，每个顶点都当一回中介点，起始点,终点
        //一个点即使起始点有时中介点又是终点，好像也无所谓
        //只要满足那个方程！
        //顺序完全没关系~
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //规定k代表的是中介点，i为起始点，j为终点
                    boolean flag = dist[i][k] != Integer.MAX_VALUE
                            && dist[k][j] != Integer.MAX_VALUE
                            && dist[i][k] + dist[k][j] < dist[i][j];
                    //取不取等无所谓，一样是不同最短路径的区别罢了
                    if (flag) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = path[k][j];//【i，j】以【k，j】为子路径
                    }

                }
            }
        }
    }



    public static void testGraphFloydWarShall() {
        String str = "12345";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('1', '2', 3);
        g.addEdge('1', '3', 8);
        g.addEdge('1', '5', -4);
        g.addEdge('2', '4', 1);
        g.addEdge('2', '5', 7);
        g.addEdge('3', '2', 4);
        g.addEdge('4', '1', 2);
        g.addEdge('4', '3', -5);
        g.addEdge('5', '4', 6);
        int[][] dist = new int[array.length][array.length];
        int[][] path = new int[array.length][array.length];
        g.floydWarShall(dist,path);
        for (int i = 0; i < array.length; i++) {
            g.printShortPath(array[i],dist[i],path[i]);
        }
    }





    public void floydWarShallBite(int[][] dist,int[][] pPath) {
//1、初始化dist数组和pPath数组
        int n = arrayV.length;
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i],Integer.MAX_VALUE);
            Arrays.fill(pPath[i],-1);
        }
//2、遍历matrix数组，把直接每个顶点直接相连的权值更新到dist数组当中
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] != Integer.MAX_VALUE) {
//存在权值 则更新dist数组
                    dist[i][j] = matrix[i][j];
//i->j 直接相连的更新完了，此时i->j的父节点下标为i
                    pPath[i][j] = i;
                }else {
//说明此时i->j 不存在直接相连
                    pPath[i][j] = -1; //这里只更新路径矩阵
                }
//i->j自己不存在距离，且没有父路径
                if(i == j) {
                    dist[i][j] = 0;
                    pPath[i][j] = j;
                }
            }
        }
//3. 上述只更新了直接相连的顶点，接下来开始考虑 以每个顶点为中转点 进行比较
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
//如果 从i->k有路径 并且 从k->j有路径
//并且 i->k + k->j 的距离小于从i直接到j 那么更新i->j的最短路径
                    if(dist[i][k] != Integer.MAX_VALUE
                            && dist[k][j] != Integer.MAX_VALUE
                            && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        pPath[i][j] = pPath[k][j];
                    }
                }
            }
    // 测试 打印权值和路径矩阵观察数据
//    for (int i = 0; i < n; i++) {
//    for (int j = 0; j < n; j++) {
//    if(dist[i][j] == Integer.MAX_VALUE) {
//    System.out.print(" * ");
//    }else{
//    System.out.print(dist[i][j]+" ");
//    }
//
//    }
//    System.out.println();
//    }
//    System.out.println("=========打印路径==========");
//    for (int i = 0; i < n; i++) {
//    for (int j = 0; j < n; j++) {
//    System.out.print(pPath[i][j]+" ");
//    }
//    System.out.println();
//    }
//    System.out.println("=================");
        }
    }
    public static void testGraphFloydWarShallBite() {
        String str = "12345";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('1', '2', 3);
        g.addEdge('1', '3', 8);
        g.addEdge('1', '5', -4);
        g.addEdge('2', '4', 1);
        g.addEdge('2', '5', 7);
        g.addEdge('3', '2', 4);
        g.addEdge('4', '1', 2);
        g.addEdge('4', '3', -5);
        g.addEdge('5', '4', 6);
        int[][] dist = new int[array.length][array.length];
        int[][] parentPath = new int[array.length][array.length];
        g.floydWarShallBite(dist,parentPath);
        for (int i = 0; i < array.length; i++) {
            g.printShortPath(array[i],dist[i],parentPath[i]);
        }
    }


//****************************************************************************************************


    public static void main4(String[] args) {
        testGraphFloydWarShall();
    }
    public static void main3(String[] args) {
        testGraphBellmanFord();
    }

    public static void main2(String[] args) {
        testGraphDijkstra();
    }
    public static void mainTree(String[] args) {
        //testGraphMinTree1();
        testGraphMinTree2();
    }

}
